package summer.graph;

import java.util.*;

public class Solution802 {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] out = new int[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                out[i]++;
                List<Integer> list = map.getOrDefault(graph[i][j], new ArrayList<>());
                list.add(i);
                map.put(graph[i][j], list);
            }
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (out[i] == 0) queue.add(i);
        }
        List<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            int cur = queue.removeFirst();
            res.add(cur);
            List<Integer> list = map.getOrDefault(cur, new ArrayList<>());
            for (int x : list) {
                out[x]--;
                if (out[x] == 0) queue.add(x);
            }
        }
        Collections.sort(res);
        return res;
    }
}
